package com.itheima.leetcode.od.b.dynamicprogramming;

import java.util.Arrays;

/**
 * (A卷,200分)- 士兵过河（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 一支N个士兵的军队正在趁夜色逃亡，途中遇到一条湍急的大河。
 * 敌军在T的时长后到达河面，没到过对岸的士兵都会被消灭。
 * 现在军队只找到了1只小船，这船最多能同时坐上2个士兵。
 * <p>
 * 当1个士兵划船过河，用时为 a[i]；0 <= i < N
 * 当2个士兵坐船同时划船过河时，用时为max(a[j],a[i])两士兵中用时最长的。
 * 当2个士兵坐船1个士兵划船时，用时为 a[i]*10；a[i]为划船士兵用时。
 * 如果士兵下河游泳，则会被湍急水流直接带走，算作死亡。
 * 请帮忙给出一种解决方案，保证存活的士兵最多，且过河用时最短。
 * <p>
 * 输入描述
 * <p>
 * 第一行：N 表示士兵数(0<N<1,000,000)
 * 第二行：T 表示敌军到达时长(0 < T < 100,000,000)
 * 第三行：a[0] a[1] … a[i]… a[N- 1]
 * a[i]表示每个士兵的过河时长。
 * (10 < a[i]< 100; 0<= i< N）
 * <p>
 * 输出描述
 * <p>
 * 第一行：”最多存活士兵数” “最短用时”
 * <p>
 * 备注
 * 1）两个士兵的同时划船时，如果划速不同则会导致船原地转圈圈；所以为保持两个士兵划速相同，则需要向划的慢的士兵看齐。
 * 2）两个士兵坐船时，重量增加吃水加深，水的阻力增大；同样的力量划船速度会变慢；
 * 3）由于河水湍急大量的力用来抵消水流的阻力，所以2）中过河用时不是a[i] *2，
 * 而是a[i] * 10。
 * <p>
 * 用例
 * <p>
 * 输入	5
 * 43
 * 12 13 15 20 50
 * 输出	3 40
 * 说明	可以达到或小于43的一种方案：
 * 第一步：a[0] a[1] 过河用时：13
 * 第二步：a[0] 返回用时：12
 * 第三步：a[0] a[2] 过河用时：15
 * <p>
 * 输入	5
 * 130
 * 50 12 13 15 20
 * 输出	5 128
 * 说明	可以达到或小于130的一种方案：
 * 第一步：a[1] a[2] 过河用时：13
 * 第二步：a[1] 返回用时：12
 * 第三步：a[0] a[4] 过河用时：50
 * 第四步：a[2] 返回用时：13
 * 第五步：a[1] a[2] 过河用时：13
 * 第六步：a[1] 返回用时：12
 * 第七步：a[1] a[3] 过河用时：15
 * 所以输出为：
 * 5 128
 * 输入	7
 * 171
 * 25 12 13 15 20 35 20
 * 输出	7 171
 * 说明
 * 可以达到或小于171的一种方案：
 * 第一步：a[1] a[2] 过桥用时：13
 * 第二步：a[1] 带火把返回用时：12
 * 第三步：a[0] a[5] 过桥用时：35
 * 第四步：a[2] 带火把返回用时：13
 * 第五步：a[1] a[2] 过桥用时：13
 * 第六步：a[1] 带火把返回用时：12
 * 第七步：a[4] a[6] 过桥用时：20
 * 第八步：a[2] 带火把返回用时：13
 * 第九步：a[1] a[3] 过桥用时：15
 * 第十步：a[1] 带火把返回用时：12
 * 第十一步：a[1] a[2] 过桥用时：13
 * <p>
 * 所以输出为：
 * <p>
 * 7 171
 * <p>
 * 题目解析
 * <p>
 * 本题是 POJ - 1700 Crossing River_伏城之外的博客-CSDN博客 的变种题。
 * <p>
 * 建议大家先搞定这题，然后再来看本题。
 * <p>
 * 本题在前面这题的基础上，多了一个过河时间限制，以及要求最多存活士兵（即在限制时间内过最多的人）
 * <p>
 * 对于贪心解法，可以结合二分法来求解本题。
 * <p>
 * 即在0~N中尝试找到成功过河的人数，其中0指的是成功过河的人数为0个，N指的是成功过河的人数为N个。
 * <p>
 * 将二分法找到的可能人数mid带入上面POJ-1700的逻辑中，计算出mid个人都过河所需的最短时间need，将need和本题过河时间限制limit进行比较：
 * <p>
 * 若 need > limit，则说明当前mid个人无法成功过河，即过河人数偏多了，我们应该减少过河人数
 * 若 need < limit，则说明当前mid个人可以成功过河，但是可能还可以过更多人数
 * 若 need == limit，则说明当前mid个人刚刚好可以在limit时间过完河，则此时mid就是最多存货的士兵数
 * 对于动态规划解法，由于是从0人过河递推到N人过河，因此不需要二分尝试过河人数，而是可以直接基于dp[i]来实时比较T，如果超过了T，则说明只能过河 i 人，耗时dp[i-1]
 * <p>
 * 另外，本题中说：
 * <p>
 * 当2个士兵坐船1个士兵划船时，用时为 a[i]*10；a[i]为划船士兵用时。
 * <p>
 * 假设x士兵划船用时为a[x]，y士兵划船用时为a[y]，a[x] < a[y]
 * <p>
 * 这句话的意思是：如果x,y一起划船，有两种过河时间，分别是：
 * <p>
 * a[x] * 10
 * a[y]
 * 如果a[y] > a[x] * 10，我们应该选择a[x] * 10，即让较快的士兵单独划船过河，这样耗时更短。
 * <p>
 * 但是，本题中又说：
 * <p>
 * (10 < a[i]< 100; 0<= i< N）
 * <p>
 * 即
 * <p>
 * 10 < a[y] < 100
 * 10 < a[x] < 100
 * 那么必然：100 < a[x] * 10 < 1000
 * <p>
 * 即必然 a[x] * 10 > a[y]
 * <p>
 * 因此，我们不需要考虑上面那种两个士兵坐船，一个士兵划船的情况。
 */
public class SoldiersCrossingRiver {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int t = sc.nextInt();*/

        int n = 5;
        int t = 43;

        int[] times = Arrays.stream("12 13 15 20 50".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(getResult(n, t, times));
    }

    public static String getResult(int n, int t, int[] times) {
        Integer[] a = Arrays.stream(times).boxed().toArray(Integer[]::new);
        Arrays.sort(a);

        int[] dp = new int[n];

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                dp[0] = a[0];
                if (dp[0] > t) {
                    return "0 0";
                }
            } else if (i == 1) {
                dp[1] = a[1];
            } else {
                dp[i] = Math.min(dp[i - 1] + a[0] + getShortTime(a[i], a[0]),
                        dp[i - 2] + a[0] + getShortTime(a[i], a[i - 1]) + a[1] + getShortTime(a[1], a[0]));
            }
            if (dp[i] > t) {
                return i + " " + dp[i - 1];
            }
        }

        return n + " " + dp[n - 1];
    }

    private static int getShortTime(Integer current, Integer pre) {
        return Math.min(current, 10 * pre);
    }
}
